package str;

import java.util.*;

/**
 * leet-code(187) 重复的DNA序列
 *
 * @author Ringo
 * @date 2021/10/8 19:48
 */
public class FindRepeatedDnaSequences {

    public static void main(String[] args) {
        String s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT";
        System.out.println(findRepeatedDnaSequences(s));
    }

    public static List<String> findRepeatedDnaSequences(String s) {
        final int step = 10;
        Set<String> set = new HashSet<>();
        Map<String, Integer> map = new HashMap<>(16);
        int n = s.length();
        for (int i = 0; i + step <= n; ++i) {
            String sub = s.substring(i, i + 10);
            Integer count = map.getOrDefault(sub, 0);
            if (count > 0) {
                set.add(sub);
            }
            map.put(sub, count + 1);
        }
        return new ArrayList<>(set);
    }

}
